1. Field of Invention
The present invention relates to estimation techniques, and more particularly, to methods and apparatus for estimating and compensating for certain types of non-Gaussian noise.
2. Discussion of Related Art
There are numerous applications that use Kalman filtering principles to estimate the state variables of dynamic systems. For example, many existing navigation systems combine GPS (global positioning system) and INS (inertial navigation system) measurements using Kalman filtering principles to achieve relatively accurate navigation. The Kalman filter is a mathematical method that estimates the state of a dynamic system, using a sequence of sensor measurements observed over time, by specifying the state transition model of the system, the observation model, and a representation of the noise in the system. When performing calculations for a Kalman filter, the state estimates and covariances are coded into matrices to handle the multiple dimensions in a single set of calculations. This allows for representation of linear relationships between different state variables (such as position, velocity, and acceleration) in any of the transition models or covariances. Noise in the sensor measurements, approximations in the system model, and/or unaccounted for external factors may all introduce uncertainty into predicted values for the state. The Kalman filter produces an estimate of the state by predicting a value of the state, estimating the uncertainty in the predicted value, and computing a weighted average of the predicted value and a new measured value of the state, with the most weight given to the value with the least uncertainty. This process is repeated over time to track the state. For example, in a navigation system to continuously provide the position of the navigator. The estimates produced by the Kalman filter lie between the measured values and the predicted values, and tend to be closer to the true values than the original measurements because the weighted average has a better estimated uncertainty than either the measured or predicted values alone.
In the navigation context, while these systems are sufficient for environments with good satellite visibility, complex environments (such as dense urban environments, for example) challenge existing Kalman-filter based systems due to the presence of significant unmodeled, non-Gaussian errors caused by phenomena such as multi-path. Multi-path occurs because the RF (radio frequency) signals are not travelling in free space between the source and destination and may be encountering reflective barriers, such as a building or topographic feature. Referring to FIG. 1, there is illustrated a diagram demonstrating the multi-path effect. A navigator 110 receives direct (non-reflected) signals 120 (solid lines) from sources 130 (e.g., GPS satellites), but also receives reflected signals 140 (dotted lines) that have reflected off buildings 150 or other obstructions. In some circumstances, the reflected signal 140 may be stronger (higher in amplitude) than the direct signal, resulting in errors in positional calculations in a navigation system; The Kalman filter model assumes that the noise in the system is Gaussian. However, errors in pseudo-ranges due to multipath are poorly approximated using Gaussian assumptions. To overcome these limitations in navigation systems, aiding information may be provided using sensors (e.g., magnetometers, Doppler radars, or cameras), databases (e.g., image databases), additional infrastructure (e.g., RF beacons), and signals of opportunity (e.g., television signals). While such approaches can provide useful aiding information, they can also experience errors that are not well modeled with Gaussian assumptions.
In addition, navigation systems using a Kalman filter in the position estimation process assume that the navigator's motion, and therefore change in position of the navigator from one estimation to the next, is smooth. However, in the presence of severe multi-path, the filtering process can compound the above-mentioned errors because the assumed relatively smooth motion becomes “jumpy,” that is, the navigator appears to move dramatically between successive estimations. As a result, there can be significant error in the estimated position of the navigation, as illustrated for example in FIG. 2. In FIG. 2, trace 210 represents the actual movement of an example receiver, and trace 220 represents the estimated movement of the example receiver using a Kalman filter, in a multi-path environment.
There are a large number of methods for dealing with non-Gaussian noise. For example, some methods include thresholding based on measurement statistics, Gauss-Markov model-based approaches, particle filters (also known as successive Monte-Carlo methods), and iterative estimators such as RANSAC (RANdom SAmple Consensus). These methods suffer from several disadvantages. For example, practical methods accounting for non-Gaussian noise are often heuristic in nature and only partially effective. Thresholding methods discard potentially useful information and require estimation of the thresholds. Methods such as the particle filter and RANSAC can be computationally expensive for realistic systems.